package backtrack;

import jdk.nashorn.internal.ir.IfNode;

import java.util.*;

/**
 * @author kaho
 * @since 2021/1/6
 */
public class _90_子集II {


    /**
     * 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     * <p>
     * 说明：解集不能包含重复的子集。
     * <p>
     * 示例:
     * <p>
     * 输入: [1,2,2]
     * 输出:
     * [
     * [2],
     * [1],
     * [1,2,2],
     * [2,2],
     * [1,2],
     * []
     * ]
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/subsets-ii
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup1(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length==0) {
            return result;
        }
        List<Integer> cur = new ArrayList<>();
        Arrays.sort(nums);
        dfs1(nums, 0, cur, result);
        return result;
    }

    private void dfs1(int[] nums, int begin, List<Integer> cur, List<List<Integer>> result) {
        result.add(new ArrayList<>(cur));
        for (int i = begin; i < nums.length; i++) {
            if (i>begin && nums[i]== nums[i-1]) {
                continue;
            }
            cur.add(nums[i]);
            dfs1(nums, i+1, cur, result);
            cur.remove(cur.size()-1);
        }
    }


    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length == 0) {
            return result;
        }
        Deque<Integer> path = new ArrayDeque<>();
        Arrays.sort(nums);
        dfs(nums, 0, path, result);
        return result;
    }

    private void dfs(int[] nums, int begin, Deque<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));
        for (int i = begin; i < nums.length; i++) {
            if (i>begin && nums[i] == nums[i-1]) {
                continue;
            }
            path.addLast(nums[i]);
            dfs(nums, i + 1, path, result);
            path.removeLast();
        }
    }
}
